// 版权归Go作者所有。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package ld

import (
	"cmd/internal/goobj"
	"cmd/internal/objabi"
	"cmd/internal/sys"
	"cmd/link/internal/loader"
	"cmd/link/internal/sym"
	"fmt"
	"internal/buildcfg"
	"unicode"
)

var _ = fmt.Print

type deadcodePass struct {
	ctxt *Link
	ldr  *loader.Loader
	wq   heap // 工作队列，使用min heap获得更好的局部性

	ifaceMethod        map[methodsig]bool // 从到达的接口调用站点调用的方法
	genericIfaceMethod map[string]bool    // 从到达的通用接口调用站点调用的方法的名称
	markableMethods    []methodref        // 到达类型的方法
	reflectSeen        bool               // 我们是否见过反射方法调用
	dynlink            bool

	methodsigstmp []methodsig // 用于解码方法签名的暂存缓冲区
}

func (d *deadcodePass) init() {
	d.ldr.InitReachable()
	d.ifaceMethod = make(map[methodsig]bool)
	d.genericIfaceMethod = make(map[string]bool)
	if buildcfg.Experiment.FieldTrack {
		d.ldr.Reachparent = make([]loader.Sym, d.ldr.NSym())
	}
	d.dynlink = d.ctxt.DynlinkingGo()

	if d.ctxt.BuildMode == BuildModeShared {
		// 标记所有当
		// 构建共享库时，此库中定义为可访问的符号。
		n := d.ldr.NDef()
		for i := 1; i < n; i++ {
			s := loader.Sym(i)
			d.mark(s, 0)
		}
		return
	}

	var names []string

	// 在普通二进制文件中，从main开始。main和init 
	// 函数，并标记从那里可以访问的内容。
	if d.ctxt.linkShared && (d.ctxt.BuildMode == BuildModeExe || d.ctxt.BuildMode == BuildModePIE) {
		names = append(names, "main.main", "main..inittask")
	} else {
		// 外部链接器直接引用主符号。
		if d.ctxt.LinkMode == LinkExternal && (d.ctxt.BuildMode == BuildModeExe || d.ctxt.BuildMode == BuildModePIE) {
			if d.ctxt.HeadType == objabi.Hwindows && d.ctxt.Arch.Family == sys.I386 {
				*flagEntrySymbol = "_main"
			} else {
				*flagEntrySymbol = "main"
			}
		}
		names = append(names, *flagEntrySymbol)
	}
	// 运行时。UnreactleMethod是一个函数，如果被调用，它将抛出。
	// 我们将无法访问的方法重定向到它。
	names = append(names, "runtime.unreachableMethod")
	if d.ctxt.BuildMode == BuildModePlugin {
		names = append(names, objabi.PathToPrefix(*flagPluginPath)+"..inittask", objabi.PathToPrefix(*flagPluginPath)+".main", "go.plugin.tabs")

		// 我们不继续前进。插件。导出符号
		// 但我们保留了它所指的符号。
		exportsIdx := d.ldr.Lookup("go.plugin.exports", 0)
		if exportsIdx != 0 {
			relocs := d.ldr.Relocs(exportsIdx)
			for i := 0; i < relocs.Count(); i++ {
				d.mark(relocs.At(i).Sym(), 0)
			}
		}
	}

	if d.ctxt.Debugvlog > 1 {
		d.ctxt.Logf("deadcode start names: %v\n", names)
	}

	for _, name := range names {
		// 将符号标记为数据/ABI0符号。
		d.mark(d.ldr.Lookup(name, 0), 0)
		if abiInternalVer != 0 {
			// 也标记任何Go函数（内部ABI）。
			d.mark(d.ldr.Lookup(name, abiInternalVer), 0)
		}
	}

	// 所有动态导出都是根。
	for _, s := range d.ctxt.dynexp {
		if d.ctxt.Debugvlog > 1 {
			d.ctxt.Logf("deadcode start dynexp: %s<%d>\n", d.ldr.SymName(s), d.ldr.SymVersion(s))
		}
		d.mark(s, 0)
	}
}

func (d *deadcodePass) flood() {
	var methods []methodref
	for !d.wq.empty() {
		symIdx := d.wq.pop()

		d.reflectSeen = d.reflectSeen || d.ldr.IsReflectMethod(symIdx)

		isgotype := d.ldr.IsGoType(symIdx)
		relocs := d.ldr.Relocs(symIdx)
		var usedInIface bool

		if isgotype {
			if d.dynlink {
				// 动态链接时，一个类型可以通过DSO 
				// 边界传递，并转换为另一端的接口。
				d.ldr.SetAttrUsedInIface(symIdx, true)
			}
			usedInIface = d.ldr.AttrUsedInIface(symIdx)
		}

		methods = methods[:0]
		for i := 0; i < relocs.Count(); i++ {
			r := relocs.At(i)
			// 当使用“-linkshared”构建时，我们无法判断是否会使用itab中的接口
			// 方法。忽略弱属性。
			if r.Weak() && !(d.ctxt.linkShared && d.ldr.IsItab(symIdx)) {
				continue
			}
			t := r.Type()
			switch t {
			case objabi.R_METHODOFF:
				if i+2 >= relocs.Count() {
					panic("expect three consecutive R_METHODOFF relocs")
				}
				if usedInIface {
					methods = append(methods, methodref{src: symIdx, r: i})
					// 方法描述符本身就是一个类型描述符，而
					// 它可以用于访问其他类型，例如通过使用
					// 反射。类型方法（一）。类型在（j）中。我们需要用UsedInFace集合遍历
					// 它的子类型。（另请参见下面的
					// 注释。）
					rs := r.Sym()
					if !d.ldr.AttrUsedInIface(rs) {
						d.ldr.SetAttrUsedInIface(rs, true)
						if d.ldr.AttrReachable(rs) {
							d.ldr.SetAttrReachable(rs, false)
							d.mark(rs, symIdx)
						}
					}
				}
				i += 2
				continue
			case objabi.R_USETYPE:
				// 用于矮人的类型符号。我们需要加载符号，但它可能无法在程序中访问。
				// 暂时不做任何事情，因为我们仍然加载所有类型符号。
				continue
			case objabi.R_USEIFACE:
				// R_USEIFACE是一个标记重新定位，它告诉链接器类型是
				// 转换为接口，即应该设置UsedInIface。请参阅下面的
				// 注释，了解我们为什么需要取消可访问位的设置并重新标记它。
				rs := r.Sym()
				if !d.ldr.AttrUsedInIface(rs) {
					d.ldr.SetAttrUsedInIface(rs, true)
					if d.ldr.AttrReachable(rs) {
						d.ldr.SetAttrReachable(rs, false)
						d.mark(rs, symIdx)
					}
				}
				continue
			case objabi.R_USEIFACEMETHOD:
				// R_USEIFACEMETHOD是一种标记重新定位的方法，用于标记所使用的接口
				// method。
				rs := r.Sym()
				if d.ctxt.linkShared && (d.ldr.SymType(rs) == sym.SDYNIMPORT || d.ldr.SymType(rs) == sym.Sxxx) {
					// 不要解码共享库中的符号（我们将标记所有导出的方法）。
					// 我们同时检查SDYNIMPORT和Sxxx，因为名称损坏的符号目前还没有得到解决。
					continue
				}
				m := d.decodeIfaceMethod(d.ldr, d.ctxt.Arch, rs, r.Add())
				if d.ctxt.Debugvlog > 1 {
					d.ctxt.Logf("reached iface method: %v\n", m)
				}
				d.ifaceMethod[m] = true
				continue
			case objabi.R_USEGENERICIFACEMETHOD:
				name := d.decodeGenericIfaceMethod(d.ldr, r.Sym())
				if d.ctxt.Debugvlog > 1 {
					d.ctxt.Logf("reached generic iface method: %s\n", name)
				}
				d.genericIfaceMethod[name] = true
				continue // 不要标记引用的符号-在最终二进制文件中不需要它。
			}
			rs := r.Sym()
			if isgotype && usedInIface && d.ldr.IsGoType(rs) && !d.ldr.AttrUsedInIface(rs) {
				// 如果将一个类型转换为接口，则可以使用反射获得一个带有“子”类型的
				// 接口（例如，从[]chan T获得一个T的
				// 接口）。我们需要使用UsedInFace属性集遍历它的“子”类型
				// 。
				// 当访问子类型（在上面的示例中为chan T）时，它将
				// 已使用InFace set，因此它将依次标记并（重新）访问其子类型
				// （例如上面的T）。
				// 我们在这里取消了可访问位的设置，因此如果子类型已经被访问，
				// 它将再次被访问。
				// 请注意，一个类型符号最多可以访问两次，一个不带
				// 使用方便，一个带。因此，终止合同仍然是有保证的。
				d.ldr.SetAttrUsedInIface(rs, true)
				d.ldr.SetAttrReachable(rs, false)
			}
			d.mark(rs, symIdx)
		}
		naux := d.ldr.NAux(symIdx)
		for i := 0; i < naux; i++ {
			a := d.ldr.Aux(symIdx, i)
			if a.Type() == goobj.AuxGotype {
				// 一个可访问的符号并不意味着我们需要它的
				// 类型描述符。不要标记它。
				continue
			}
			d.mark(a.Sym(), symIdx)
		}
		// 某些主机对象符号有一个外部对象，其作用类似于
		// “载体”符号，或者它包含特定
		// 部分的所有符号。我们需要标记该运营商的所有“参考”符号，
		// 因此我们要确保引入所有外部符号及其子
		// 符号。这并不理想，这些载体/部分符号可能会被删除。
		if d.ldr.IsExternal(symIdx) {
			d.mark(d.ldr.OuterSym(symIdx), symIdx)
			d.mark(d.ldr.SubSym(symIdx), symIdx)
		}

		if len(methods) != 0 {
			if !isgotype {
				panic("method found on non-type symbol")
			}
			// 解码类型方法的运行时类型信息
			// 帮助解决哪些方法可以通过接口动态调用
			// 的问题。
			methodsigs := d.decodetypeMethods(d.ldr, d.ctxt.Arch, symIdx, &relocs)
			if len(methods) != len(methodsigs) {
				panic(fmt.Sprintf("%q has %d method relocations for %d methods", d.ldr.SymName(symIdx), len(methods), len(methodsigs)))
			}
			for i, m := range methodsigs {
				methods[i].m = m
				if d.ctxt.Debugvlog > 1 {
					d.ctxt.Logf("markable method: %v of sym %v %s\n", m, symIdx, d.ldr.SymName(symIdx))
				}
			}
			d.markableMethods = append(d.markableMethods, methods...)
		}
	}
}

func (d *deadcodePass) mark(symIdx, parent loader.Sym) {
	if symIdx != 0 && !d.ldr.AttrReachable(symIdx) {
		d.wq.push(symIdx)
		d.ldr.SetAttrReachable(symIdx, true)
		if buildcfg.Experiment.FieldTrack && d.ldr.Reachparent[symIdx] == 0 {
			d.ldr.Reachparent[symIdx] = parent
		}
		if *flagDumpDep {
			to := d.ldr.SymName(symIdx)
			if to != "" {
				if d.ldr.AttrUsedInIface(symIdx) {
					to += " <UsedInIface>"
				}
				from := "_"
				if parent != 0 {
					from = d.ldr.SymName(parent)
					if d.ldr.AttrUsedInIface(parent) {
						from += " <UsedInIface>"
					}
				}
				fmt.Printf("%s -> %s\n", from, to)
			}
		}
	}
}

func (d *deadcodePass) markMethod(m methodref) {
	relocs := d.ldr.Relocs(m.src)
	d.mark(relocs.At(m.r).Sym(), m.src)
	d.mark(relocs.At(m.r+1).Sym(), m.src)
	d.mark(relocs.At(m.r+2).Sym(), m.src)
}

// 死码标记所有可到达的符号。
// 
// 消除死代码的基础是大量的符号，
// 在重新定位之后，从*flagEntrySymbol开始。wen jian defg
// 所有方法都是通过在接收器的*rtype上重新定位来提及的。
// 这些重定位由编译器
// 专门定义为R_METHODOFF，因此我们可以在这里检测和操作它们。
// 
// 有三种方法可以调用可访问类型的方法：
// 
// 1。直接拨打
// 2。通过一个可访问的接口类型
// 3。反映价值方法（或MethodByName）或reflect。类型方法
// （或MethodByName）
// 
// 第一个病例由洪水填充处理，直接调用的方法
// 标记为可达。
// 
// 第二种情况是通过将所有可访问的接口
// 类型分解为方法签名来处理的。将遇到的每个方法与接口方法签名进行比较，如果匹配，则将其标记为
// 可访问。这是非常保守的，但简单而正确。
// 
// 第三个案例通过查看以下任何一项来处理：
// /-。价值方法或MethodByName可访问
// /-reflect。类型方法或MethodByName被调用（通过编译器标记的
// REFLECTMETHOD属性）。
// 如果出现任何一种情况，则所有赌注都将被取消，可访问类型的所有导出方法
// 都标记为可访问。
// 
// 将从ctxt中删除所有未读取的文本符号。Textp。
func deadcode(ctxt *Link) {
	ldr := ctxt.loader
	d := deadcodePass{ctxt: ctxt, ldr: ldr}
	d.init()
	d.flood()

	methSym := ldr.Lookup("reflect.Value.Method", abiInternalVer)
	methByNameSym := ldr.Lookup("reflect.Value.MethodByName", abiInternalVer)

	if ctxt.DynlinkingGo() {
		// 当动态链接时，导出的方法可能会满足我们还不知道的接口。
		d.reflectSeen = true
	}

	for {
		// 可以通过反射调用方法。放弃静态分析，将所有导出的方法标记为可访问。
		d.reflectSeen = d.reflectSeen || (methSym != 0 && ldr.AttrReachable(methSym)) || (methByNameSym != 0 && ldr.AttrReachable(methByNameSym))

		// 将所有能够满足已发现的
		// 接口的方法标记为可访问。我们重新检查了旧的标记接口
		// 因为在上一次检查中可能发现了新类型（使用新方法）。
		rem := d.markableMethods[:0]
		for _, m := range d.markableMethods {
			if (d.reflectSeen && (m.isExported() || d.dynlink)) || d.ifaceMethod[m.m] || d.genericIfaceMethod[m.m.name] {
				d.markMethod(m)
			} else {
				rem = append(rem, m)
			}
		}
		d.markableMethods = rem

		if d.wq.empty() {
			// 没有发现新的工作。完成。
			break
		}
		d.flood()
	}
}

// methodsig是一个类型化的方法签名（名称+类型）。
type methodsig struct {
	name string
	typ  loader.Sym // 函数的类型描述符符号
}

// methodref保存从接收器类型符号到其
// 方法的重定位。共有三次重新定位，
// reflect中的每个字段一次。方法结构：mtyp、ifn和tfn。
type methodref struct {
	m   methodsig
	src loader.Sym // 接收器类型符号
	r   int        // R_METHODOFF重定位的索引
}

func (m methodref) isExported() bool {
	for _, r := range m.m.name {
		return unicode.IsUpper(r)
	}
	panic("methodref has no signature")
}

// 解码方法SIG解码方法签名信息数组。
// 数组的每个元素都是大小字节。前4个字节是
// nameOff，表示方法名，后4个字节是typeOff，表示函数类型。
// 
// 这是两个运行时的布局。方法和运行时。我的方法。
func (d *deadcodePass) decodeMethodSig(ldr *loader.Loader, arch *sys.Arch, symIdx loader.Sym, relocs *loader.Relocs, off, size, count int) []methodsig {
	if cap(d.methodsigstmp) < count {
		d.methodsigstmp = append(d.methodsigstmp[:0], make([]methodsig, count)...)
	}
	var methods = d.methodsigstmp[:count]
	for i := 0; i < count; i++ {
		methods[i].name = decodetypeName(ldr, symIdx, relocs, off)
		methods[i].typ = decodeRelocSym(ldr, symIdx, relocs, int32(off+4))
		off += size
	}
	return methods
}

// 在offset off处解码接口类型符号symIdx的方法。
func (d *deadcodePass) decodeIfaceMethod(ldr *loader.Loader, arch *sys.Arch, symIdx loader.Sym, off int64) methodsig {
	p := ldr.Data(symIdx)
	if p == nil {
		panic(fmt.Sprintf("missing symbol %q", ldr.SymName(symIdx)))
	}
	if decodetypeKind(arch, p)&kindMask != kindInterface {
		panic(fmt.Sprintf("symbol %q is not an interface", ldr.SymName(symIdx)))
	}
	relocs := ldr.Relocs(symIdx)
	var m methodsig
	m.name = decodetypeName(ldr, symIdx, &relocs, int(off))
	m.typ = decodeRelocSym(ldr, symIdx, &relocs, int32(off+4))
	return m
}

// 解码存储在symIdx符号中的方法名。符号应该只包含方法名的字节。
func (d *deadcodePass) decodeGenericIfaceMethod(ldr *loader.Loader, symIdx loader.Sym) string {
	return string(ldr.Data(symIdx))
}

func (d *deadcodePass) decodetypeMethods(ldr *loader.Loader, arch *sys.Arch, symIdx loader.Sym, relocs *loader.Relocs) []methodsig {
	p := ldr.Data(symIdx)
	if !decodetypeHasUncommon(arch, p) {
		panic(fmt.Sprintf("no methods on %q", ldr.SymName(symIdx)))
	}
	off := commonsize(arch) // 反映。rtype 
	switch decodetypeKind(arch, p) & kindMask {
	case kindStruct: // 反射。结构类型
		off += 4 * arch.PtrSize
	case kindPtr: // 反射。pRTYPE 
		off += arch.PtrSize
	case kindFunc: // 反映。funcType 
		off += arch.PtrSize // 4字节，指针对齐
	case kindSlice: // reflect。切片类型
		off += arch.PtrSize
	case kindArray: // 反射。阵列类型
		off += 3 * arch.PtrSize
	case kindChan: // 反射。chanType 
		off += 2 * arch.PtrSize
	case kindMap: // 反射。映射类型
		off += 4*arch.PtrSize + 8
	case kindInterface: // 反射。interfaceType 
		off += 3 * arch.PtrSize
	default:
		// 刚好是大小（rtype）
	}

	mcount := int(decodeInuxi(arch, p[off+4:], 2))
	moff := int(decodeInuxi(arch, p[off+4+2+2:], 4))
	off += moff                // 偏移到反射数组。方法值
	const sizeofMethod = 4 * 4 // sizeof reflect。程序
	return d.decodeMethodSig(ldr, arch, symIdx, relocs, off, sizeofMethod, mcount)
}
